|
In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from breadth first search, but it produces an ordering that is consistent with breadth-first search. The lexicographic breadth-first search algorithm is based on the idea of partition refinement and was first developed by . A more detailed survey of the topic is presented by . It has been used as a subroutine in other graph algorithms including the recognition of chordal graphs, and optimal coloring of distance-hereditary graphs. ==Algorithm== The lexicographic breadth-first search algorithm replaces the queue of vertices of a standard breadth-first search with an ordered sequence of sets of vertices. The sets in the sequence form a partition of the remaining vertices. At each step, a vertex ''v'' from the first set in the sequence is removed from that set, and if that removal causes the set to become empty then the set is removed from the sequence. Then, each set in the sequence is replaced by two subsets: the neighbors of ''v'' and the non-neighbors of ''v''. The subset of neighbors is placed earlier in the sequence than the subset of non-neighbors. In pseudocode, the algorithm can be expressed as follows: *Initialize a sequence Σ of sets, to contain a single set containing all vertices. *Initialize the output sequence of vertices to be empty. *While Σ is non-empty: * *Find and remove a vertex ''v'' from the first set in Σ * *If the first set in Σ is now empty, remove it from Σ * *Add ''v'' to the end of the output sequence. * *For each edge ''v-w'' such that ''w'' still belongs to a set ''S'' in Σ: * * *If the set ''S'' containing ''w'' has not yet been replaced while processing ''v'', create a new empty replacement set ''T'' and place it prior to ''S'' in the sequence; otherwise, let ''T'' be the set prior to ''S''. * * *Move ''w'' from ''S'' to ''T'', and if this causes ''S'' to become empty remove ''S'' from Σ. Each vertex is processed once, each edge is examined only when its two endpoints are processed, and (with an appropriate representation for the sets in Σ that allows items to be moved from one set to another in constant time) each iteration of the inner loop takes only constant time. Therefore, like simpler graph search algorithms such as breadth-first search and depth first search, this algorithm takes linear time. The algorithm is called lexicographic breadth-first search because the order it produces is an ordering that could also have been produced by a breadth-first search, and because if the ordering is used to index the rows and columns of an adjacency matrix of a graph then the algorithm sorts the rows and columns into Lexicographical order. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lexicographic breadth-first search」の詳細全文を読む スポンサード リンク
|